package com.LC._200;

import java.net.Socket;

//class Solution {
//    public int numIslands(char[][] grid) {
//        int islandNum = 0;
//        for(int i = 0; i < grid.length; i++){//row
//            for(int j = 0; j < grid[0].length; j++){//col
//                if(grid[i][j] == '1'){
//                    //找到陆地时开始搜索
//                    infect(grid, i, j);//
//                    //找不到陆地结束搜索
//                    islandNum++;
//                }
//            }
//        }
//        return islandNum;
//    }
//    //感染函数
//    public void infect(char[][] grid, int i, int j){
//        //终止条件 超过上下左右边界||遇到0
//        if(i < 0 || i >= grid.length ||
//                j < 0 || j >= grid[0].length || grid[i][j] != '1'){
//            return;//返回上一级递归
//        }
//        //深度优先搜索 递归函数传参level+1
//        grid[i][j] = '2';
//        infect(grid, i + 1, j);//相邻的两个递归函数==第一个先递归到终点在开始第二的递归
//        infect(grid, i - 1, j);
//        infect(grid, i, j + 1);
//        infect(grid, i, j - 1);
//    }
//
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//
//        char[][] s = new char[][]  {{'0', '0', '1', '1', '0'},
//                                    {'0', '1', '0', '1', '0'},
//                                    {'1', '1', '0', '0', '1'},
//                                    {'0', '0', '1', '1', '0'}};
//
//
//        System.out.println(solution.numIslands(s));
//    }
//}
class Solution {
    public int numIslands(char[][] grid) {
        int res=0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
           if(grid[i][j]=='1'){
                    infect(grid , i ,j);
                    res++;
                }
            }
        }
        return res;
    }

    private void infect(char[][] grid, int i, int j) {
        if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j] != '1'){
            return;//不必返回值
        }
        grid[i][j]=2;
        infect(grid , i , j-1);
        infect(grid , i+1 , j);
        infect(grid , i , j+1);
        infect(grid , i-1, j);


    }


    public static void main(String[] args) {
    Solution solution = new Solution();

          char[][] s = new char[][]{{'0', '0', '1', '1', '0'},
                                    {'0', '1', '0', '1', '0'},
                                    {'1', '1', '0', '0', '1'},
                                    {'0', '0', '1', '1', '0'}};

//
        System.out.println(solution.numIslands(s));
    }
}